package com.example.demo.algorithm4th.qr3_search;

/**
 * @author wangsl
 * @date 2020/6/20 13:22
 * <p>
 * Description:查找有序数组中的数据位置，使用二分法查找并递归定位数据位置
 */
public class BinarySearchAndRecursiveIndex {
    public int get(int[] data, int key) {
        return get(data, key,0, data.length-1);
    }

    public int get(int[] data, int key,int low,int high){
        int idx = -1;
        //未找到，跳出递归,-1表示未找到
        if (low == high && key != data[low]) {
            return idx;
        }
        int mid = (low + high) / 2;
        if (key < data[mid]) {
            idx = get(data, key, low, mid - 1);//不能取mid
        } else if (key > data[mid]) {
            idx = get(data, key, mid + 1, high);//不能取mid
        } else {
            idx = mid;
        }
        return idx;
    }

    public static void main(String[] args) {
        int data[] = {1, 3, 4, 5, 6, 7, 11};
//        int key = 11;
//        int key = 13;
//        int key = 9;
        int key = 3;
        BinarySearchAndRecursiveIndex binary = new BinarySearchAndRecursiveIndex();
        int index = binary.get(data, key);
        System.out.println(index);
    }
}
